Since the early days of the electronic computer, some of the most ambitious goals in computer science research were in the field of Artificial Intelligence. To date computer power has increased by many orders of magnitude (powers of ten). Utilizing the immense power of computers available today computer engineers are exploring various practical uses of computers within a sub-field of Artificial Intelligence known as Machine Learning. In Machine Learning a goal is to provide hardware and/or software that enables a computer to learn to perform particular task, such as distinguishing different spoken or handwritten words.
One sub-field of Machine Learning is Genetic Programming. A goal of Genetic Programming is to make a computer automatically generate a computer program (i.e. a sequence of instructions) to perform a particular task that uses the computer. In Genetic Programming, programs in successive generations of a population of programs being evolved are selected based on fitness to solve test cases of a particular problem and the selected programs are cross-bread and mutated to form each next generation.
One type of Genetic Programming is called Gene Expression Programming (GEP). In Gene Expression Programming the computer programs being evolved are represented by vectors of program tokens, called chromosomes. In the course of evolving a population of vector representations of programs various evolutionary operations such as one-point cross-over, two-point cross-over and mutation are performed. Gene Expression Programming is described in issued U.S. Pat. No. 7,127,436 to Weimin Xiao et al, in co-pending patent application publication Number US 2006-0200436 A1 by Chi Zhou et al., published Sep. 7, 2006 and in Candida Ferreira, “Gene Expression Programming: a New Adaptive Algorithm for Solving Problems,” Complex Systems, Vol. 13, No. 2, pages 87-129, 2001.
In computer programming the order of execution of instructions is important. However, the evolutionary operations used in Gene Expression Programming are not particularly attuned to the importance of the order of execution in computer programs, or the importance of an instruction at a typical position in the execution sequence. For example a one-point cross-over operation exchanges a first part of a program encoded in a GEP chromosome with a last part of a program encoded in another GEP chromosome. Another negative aspect of GEP is that even using current high speed computers, even using highly parallel computers GEP software often requires very long run times, particularly for complex problems.
Thus, it is highly desired to have an improved GEP more suitable for automatically generating computer programs and requires less run time.
Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.